package BFS;

import java.util.*;

public class Solution773 {

    //用来指示位于index上的0元素应该找哪个索引的元素交换位置
    public static int[][] map = new int[][]{
            {1,3},
            {0,4,2},
            {1,5},
            {0,4},
            {1,3,5},
            {2,4}
    };


    //开始手搓BFS遍历模板
    public int slidingPuzzle(int[][] board) {
        String target = "123450";
        String start="";
        int step = 0;

        //将二维数组转化为String
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                start = start + board[i][j];
            }
        }

        //用boolean数组怕是不中用了。。
        HashSet<String> visited = new HashSet<>();
        //依旧队列
        Queue<String> q = new LinkedList<>();

        //将起始位置加入队列中
        q.offer(start);
        //visited哈希集合中加入start
        visited.add(start);

        while(!q.isEmpty()){
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                if (cur.equals(target)){
                    return step;
                }

                for (String neighbor : getNeighbors(cur)) {
                    if (!visited.contains(neighbor)){
                        q.offer(neighbor);
                        visited.add(neighbor);
                    }
                }
            }

            step++;
        }
        //走到这一步，已经是失败了
        return -1;
    }

    public List<String> getNeighbors(String board){
        //先找到0所处在的索引，然后把0和上下左右的元素交换
        int index = board.indexOf('0');
        List<String> neighbors = new ArrayList<>();
        for (int i = 0; i < map[index].length; i++) {
            String neighbor = swap(board.toCharArray(),index,map[index][i]);
            neighbors.add(neighbor);
        }

        return neighbors;
    }

    public String swap(char[] board,int arg1,int arg2){
        char temp = board[arg1];
        board[arg1] = board[arg2];
        board[arg2] = temp;

        return new String(board);
    }
}
